import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution473 {

    public static void main(String args[]) {
        Solution473 s = new Solution473();
        System.out.println(s.makesquare(new int[]{19, 13, 2, 7, 13, 17, 9, 8, 7, 9, 3, 11, 6, 8, 19}));
    }

    public boolean makesquare(int[] nums) {
        if (nums.length == 0) {
            return false;
        }
        Arrays.sort(nums);
        int[] nnums = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            nnums[i] = nums[nums.length - i - 1];
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        int len = sum / 4;
        return dfs(nnums, 0, new int[4], len);
    }

    public boolean dfs(int[] nums, int st, int[] mp, int len) {
        if (st == nums.length) {
            return true;
        }
        for (int i = 0; i < 4; i++) {
            if (mp[i] + nums[st] <= len) {
                mp[i] += nums[st];
                if (dfs(nums, st + 1, mp, len)) {
                    return true;
                }
                mp[i] -= nums[st];
            }
        }
        return false;
    }


}
